class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(num.begin(), num.end());
        int n = num.size();
        vector<int> record(3);
        vector<vector<int> > ans;

        for (int i = 0; i < n; ) {
            for (int j = i + 1, k = n - 1; j < k; ) {
                while (j < k && num[i] + num[j] + num[k] > 0) {
                    --k;
                }
                if (j == k) {
                    break;
                }
                if (num[i] + num[j] + num[k] == 0) {
                    record[0] = num[i];
                    record[1] = num[j];
                    record[2] = num[k];
                    ans.push_back(record);
                }
                int x = j + 1;
                while (x < k && num[x] == num[j]) {
                    ++x;
                }
                j = x;
            }
            int x = i + 1;
            while (x < n && num[x] == num[i]) {
                ++x;
            }
            i = x;
        }
        return ans;
    }
};
